package com.sheng.leetcode.year2025.month09.day17;

import org.junit.Test;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author by ls
 * @date 2025/9/17
 * <p>
 * 2349. 设计数字容器系统<p>
 * <p>
 * 设计一个数字容器系统，可以实现以下功能：<p>
 * 在系统中给定下标处 插入 或者 替换 一个数字。<p>
 * 返回 系统中给定数字的最小下标。<p>
 * 请你实现一个 NumberContainers 类：<p>
 * NumberContainers() 初始化数字容器系统。<p>
 * void change(int index, int number) 在下标 index 处填入 number 。<p>
 * 如果该下标 index 处已经有数字了，那么用 number 替换该数字。<p>
 * int find(int number) 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ，那么返回 -1 。<p>
 * <p>
 * 示例：<p>
 * 输入：<p>
 * ["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]<p>
 * [[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]<p>
 * 输出：<p>
 * [null, -1, null, null, null, null, 1, null, 2]<p>
 * 解释：<p>
 * NumberContainers nc = new NumberContainers();<p>
 * nc.find(10); // 没有数字 10 ，所以返回 -1 。<p>
 * nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。<p>
 * nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。<p>
 * nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。<p>
 * nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。<p>
 * nc.find(10); // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。<p>
 * nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。<p>
 * nc.find(10); // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。<p>
 * <p>
 * 提示：<p>
 * 1 <= index, number <= 10^9<p>
 * 调用 change 和 find 的 总次数 不超过 10^5 次。<p>
 */
public class LeetCode2349 {

    @Test
    public void test() {
        NumberContainers nc = new NumberContainers();
        // 没有数字 10 ，所以返回 -1 。
        System.out.println(nc.find(10));
        // 容器中下标为 2 处填入数字 10 。
        nc.change(2, 10);
        // 容器中下标为 1 处填入数字 10 。
        nc.change(1, 10);
        // 容器中下标为 3 处填入数字 10 。
        nc.change(3, 10);
        // 容器中下标为 5 处填入数字 10 。
        nc.change(5, 10);
        // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。
        System.out.println(nc.find(10));
        // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。
        nc.change(1, 20);
        // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。
        System.out.println(nc.find(10));
    }
}

class NumberContainers {

    private Map<Integer, PriorityQueue<Integer>> map1;
    private Map<Integer, Integer> map2;

    /**
     * 初始化数字容器系统
     */
    public NumberContainers() {
        // 空间换时间
        // 存储 2 个
        // 一个通过数字查询索引，索引按照时间排序
        map1 = new HashMap<>();
        // 一个存储当前索引对应的数字
        map2 = new HashMap<>();
    }

    /**
     * 在下标 index 处填入 number 。
     * 如果该下标 index 处已经有数字了，那么用 number 替换该数字
     *
     * @param index  下标
     * @param number 数字
     */
    public void change(int index, int number) {
        if (map2.containsKey(index)) {
            // 下标 index 处已经有数字了，那么用 number 替换该数字
            Integer i = map2.get(index);
            // 下标处的数字和之前一样，那么无需进行操作
            if (i != number) {
                // 下标数字和之前的不一致，需要先减去之前数字对应的下标集合中的 i，如果此时刚好下标为空，那么直接删除该数字
                PriorityQueue<Integer> integers = map1.get(i);
                integers.remove(index);
                if (integers.isEmpty()) {
                    map1.remove(i);
                } else {
                    map1.put(i, integers);
                }
                // 然后将当前数字和之前数字进行替换
                map2.put(index, number);
                PriorityQueue<Integer> orDefault = map1.getOrDefault(number, new PriorityQueue<>(Comparator.naturalOrder()));
                orDefault.add(index);
                map1.put(number, orDefault);
            }
        } else {
            // 在下标 index 处填入 number
            map2.put(index, number);
            PriorityQueue<Integer> integers = map1.get(number);
            if (integers == null) {
                integers = new PriorityQueue<>(Comparator.naturalOrder());
            }
            integers.add(index);
            map1.put(number, integers);
        }
    }

    /**
     * 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ，那么返回 -1 。
     *
     * @param number 数字
     * @return 最小下标
     */
    public int find(int number) {
        if (map1.containsKey(number)) {
            // 下标 index 处已经有数字了，那么用 number 替换该数字
            return map1.get(number).peek();
        } else {
            // 如果系统中没有 number ，那么返回 -1
            return -1;
        }
    }
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers obj = new NumberContainers();
 * obj.change(index,number);
 * int param_2 = obj.find(number);
 */
